ラボ8：グラフを用いたソーシャルネットワーク

目標 🎯

  • モデル： 単純なソーシャルネットワーク。
    • ユーザーはグラフのノードとして表現されます。
    • 友達関係は無向辺です。
  • 課題： コマンドの系列を処理して、ネットワークを構築し、照会します。

表現方法 💾

グラフを格納するために隣接リストを使用します。

これはリストの配列です。インデックス `i` のリストには、ユーザー `i` のすべての友達が格納されています。

// 友達関係: (0,1), (0,2), (1,2)
adj = [
0:[1, 2],
1:[0, 2],
2:[0, 1],
3:[],
]

操作 ⚙️

以下の4つのコマンドを実装します：

  • add u v

    友達関係を追加する。

  • degree u

    ユーザー u の友達数をカウントする。

  • isfriend u v

    u と v が友達かどうか確認する。

  • count_greater x

    友達数が x より多いユーザー数をカウントする。